package com.ayu.a.chapter04;

/**
 * @Author 徐林玉
 * @Description QuickSort
 * @Date 2022/11/4 13:58
 * @Version 1.0
 */
public class QuickSort {

    public static void main(String[] args) {

        int[] arr = new int[]{25,1,5,28,7};

//        quickSort(arr, 0, 4);

        quickSort(arr, 0, 4);
        for (int i = 0; i < arr.length; i++) {

            System.out.print(arr[i] + "  ");

        }


    }


    /**
     * 入口函数（递归方法），算法的调用从这里开始。
     */
    public static void quickSort(int[] arr, int startIndex, int endIndex) {
        if (startIndex >= endIndex) {
            return;
        }

        // 核心算法部分：分别介绍 双边指针（交换法），双边指针（挖坑法），单边指针
        int pivotIndex = doublePointerSwap(arr, startIndex, endIndex);
        // int pivotIndex = doublePointerHole(arr, startIndex, endIndex);
        // int pivotIndex = singlePointer(arr, startIndex, endIndex);

        // 用分界值下标区分出左右区间，进行递归调用
        quickSort(arr, startIndex, pivotIndex - 1);
        quickSort(arr, pivotIndex + 1, endIndex);
    }

    /**
     * 双边指针（交换法）
     * 思路：
     * 记录分界值 pivot，创建左右指针（记录下标）。
     * （分界值选择方式有：首元素，随机选取，三数取中法）
     *
     * 首先从右向左找出比pivot小的数据，
     * 然后从左向右找出比pivot大的数据，
     * 左右指针数据交换，进入下次循环。
     *
     * 结束循环后将当前指针数据与分界值互换，
     * 返回当前指针下标（即分界值下标）
     */
    private static int doublePointerSwap(int[] arr, int startIndex, int endIndex) {
        int pivot = arr[startIndex];
        int leftPoint = startIndex;
        int rightPoint = endIndex;

        while (leftPoint < rightPoint) {

            // 从右向左找出比pivot小的数据
            while (leftPoint < rightPoint
                    && arr[rightPoint] > pivot) {
                rightPoint--;
            }
            // 从左向右找出比pivot大的数据
            while (leftPoint < rightPoint
                    && arr[leftPoint] <= pivot) {
                leftPoint++;
            }


            // 没有过界则交换
            if (leftPoint < rightPoint) {
                int temp = arr[leftPoint];
                arr[leftPoint] = arr[rightPoint];
                arr[rightPoint] = temp;
            }
        }
        // 最终将分界值与当前指针数据交换
        arr[startIndex] = arr[rightPoint];
        arr[rightPoint] = pivot;
        // 返回分界值所在下标
        return rightPoint;
    }


//    public static void quicksort(int[] arr, int low, int high) {
//        //少了这个条件就栈溢出了
//        if (low > high) {
//            return;
//        }
//
//        //两个指针
//        int i = low;
//        int j = high;
//
//        //临时变量，用于交换
//        int temp;
//
//        //基准值（通常选用第一个元素）
//        int rvalue = arr[low];
//
//        //交换顺序（大于基准去右边，小于基准去左边）(循环，直到i=j)
//        while (i < j) {
//            //j先从右边往左边走,如果j位置上的数比基准小就停下
//            while (rvalue <= arr[j] && i < j) {
//                j--;
//            }
//
//            //i先从左边往右边走,如果i位置上的数比基准大就停下
//            while (rvalue >= arr[i] && i < j) {
//                i++;
//            }
//
//            //如果i和j位置上的数都满足要求（i位置数比基准大，j位置数比基准小，交换位置）
//            if (i < j) {
//                temp = arr[i];
//                arr[i] = arr[j];
//                arr[j] = temp;
//            }
//        }
//
//        //当i=j时，将i=j位置上的值和基准交换
//        arr[low] = arr[i];
//        arr[i] = rvalue;
//
//
//        //递归调用左侧和右侧半数组
//
//        quicksort(arr, low, j - 1);
//        quicksort(arr, j + 1, high);
//
//
//    }
//
//
//    public static void quickSort(int[] arr, int startIndex, int endIndex) {
//
//        if (startIndex >= endIndex) {
//
//            return;
//        }
//
//        Integer pivotIndex = doublePointSwap(arr, startIndex, endIndex);
//
//        quickSort(arr, startIndex, pivotIndex - 1);
//
//        quickSort(arr, pivotIndex + 1, endIndex);
//    }
//
//
//    public static Integer doublePointSwap(int[] arr, int startIndex, int endIndex) {
//
//
//        int pivot = arr[startIndex];
//
//        int leftPoint = startIndex;
//
//        int rightPoint = endIndex;
//
//        while (leftPoint < rightPoint) {
//
//            //从左往右找到比pivot大的数
//
//            while (leftPoint < rightPoint && arr[leftPoint] <= pivot) {
//
//                leftPoint++;
//            }
//            //从右往左找到比pivot小的数
//            while (leftPoint < rightPoint && arr[rightPoint] >= pivot) {
//                rightPoint--;
//            }
//
//            if (leftPoint < rightPoint) {
//
//                int temp = arr[leftPoint];
//
//                arr[leftPoint] = arr[rightPoint];
//
//                arr[rightPoint] = temp;
//            }
//        }
//
//        //当leftpoint 与rightpoint交叉时候 就是新的 pivot
//
//        arr[startIndex] = arr[leftPoint];
//
//        arr[leftPoint] = pivot;
//
//        return leftPoint;
//    }
}
